

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>2.19 实现一个简单的递归下降分析器 &mdash; python3-cookbook 3.0.0 documentation</title>
  

  
  
  
  

  

  
  
    

  

  <link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
    <link rel="next" title="2.20 字节字符串上的字符串操作" href="p20_perform_text_operations_on_byte_string.html" />
    <link rel="prev" title="2.18 字符串令牌解析" href="p18_tokenizing_text.html" /> 

  
  <script src="../_static/js/modernizr.min.js"></script>

</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search">
          

          
            <a href="../index.html" class="icon icon-home"> python3-cookbook
          

          
          </a>

          
            
            
              <div class="version">
                3.0
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../chapters/p01_data_structures_algorithms.html">第一章：数据结构和算法</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../chapters/p02_strings_and_text.html">第二章：字符串和文本</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="p01_split_string_on_multiple_delimiters.html">2.1 使用多个界定符分割字符串</a></li>
<li class="toctree-l2"><a class="reference internal" href="p02_match_text_at_start_end.html">2.2 字符串开头或结尾匹配</a></li>
<li class="toctree-l2"><a class="reference internal" href="p03_match_strings_with_shell_wildcard.html">2.3 用Shell通配符匹配字符串</a></li>
<li class="toctree-l2"><a class="reference internal" href="p04_match_and_search_text.html">2.4 字符串匹配和搜索</a></li>
<li class="toctree-l2"><a class="reference internal" href="p05_search_and_replace_text.html">2.5 字符串搜索和替换</a></li>
<li class="toctree-l2"><a class="reference internal" href="p06_search_replace_case_insensitive.html">2.6 字符串忽略大小写的搜索替换</a></li>
<li class="toctree-l2"><a class="reference internal" href="p07_specify_regexp_for_shortest_match.html">2.7 最短匹配模式</a></li>
<li class="toctree-l2"><a class="reference internal" href="p08_regexp_for_multiline_partterns.html">2.8 多行匹配模式</a></li>
<li class="toctree-l2"><a class="reference internal" href="p09_normalize_unicode_text_to_regexp.html">2.9 将Unicode文本标准化</a></li>
<li class="toctree-l2"><a class="reference internal" href="p10_work_with_unicode_in_regexp.html">2.10 在正则式中使用Unicode</a></li>
<li class="toctree-l2"><a class="reference internal" href="p11_strip_unwanted_characters.html">2.11 删除字符串中不需要的字符</a></li>
<li class="toctree-l2"><a class="reference internal" href="p12_sanitizing_clean_up_text.html">2.12 审查清理文本字符串</a></li>
<li class="toctree-l2"><a class="reference internal" href="p13_aligning_text_strings.html">2.13 字符串对齐</a></li>
<li class="toctree-l2"><a class="reference internal" href="p14_combine_and_concatenate_strings.html">2.14 合并拼接字符串</a></li>
<li class="toctree-l2"><a class="reference internal" href="p15_interpolating_variables_in_strings.html">2.15 字符串中插入变量</a></li>
<li class="toctree-l2"><a class="reference internal" href="p16_reformat_text_to_fixed_number_columns.html">2.16 以指定列宽格式化字符串</a></li>
<li class="toctree-l2"><a class="reference internal" href="p17_handle_html_xml_in_text.html">2.17 在字符串中处理html和xml</a></li>
<li class="toctree-l2"><a class="reference internal" href="p18_tokenizing_text.html">2.18 字符串令牌解析</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">2.19 实现一个简单的递归下降分析器</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#id2">问题</a></li>
<li class="toctree-l3"><a class="reference internal" href="#id3">解决方案</a></li>
<li class="toctree-l3"><a class="reference internal" href="#id6">讨论</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="p20_perform_text_operations_on_byte_string.html">2.20 字节字符串上的字符串操作</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../aboutme.html">关于</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../index.html">python3-cookbook</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../index.html">Docs</a> &raquo;</li>
        
          <li><a href="../chapters/p02_strings_and_text.html">第二章：字符串和文本</a> &raquo;</li>
        
      <li>2.19 实现一个简单的递归下降分析器</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
            <a href="../_sources/c02/p19_writing_recursive_descent_parser.rst.txt" rel="nofollow"> View page source</a>
          
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="id1">
<h1>2.19 实现一个简单的递归下降分析器<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h1>
<div class="section" id="id2">
<h2>问题<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h2>
<p>你想根据一组语法规则解析文本并执行命令，或者构造一个代表输入的抽象语法树。
如果语法非常简单，你可以自己写这个解析器，而不是使用一些框架。</p>
</div>
<div class="section" id="id3">
<h2>解决方案<a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h2>
<p>在这个问题中，我们集中讨论根据特殊语法去解析文本的问题。
为了这样做，你首先要以BNF或者EBNF形式指定一个标准语法。
比如，一个简单数学表达式语法可能像下面这样：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">expr</span> <span class="o">+</span> <span class="n">term</span>
    <span class="o">|</span>   <span class="n">expr</span> <span class="o">-</span> <span class="n">term</span>
    <span class="o">|</span>   <span class="n">term</span>

<span class="n">term</span> <span class="p">::</span><span class="o">=</span> <span class="n">term</span> <span class="o">*</span> <span class="n">factor</span>
    <span class="o">|</span>   <span class="n">term</span> <span class="o">/</span> <span class="n">factor</span>
    <span class="o">|</span>   <span class="n">factor</span>

<span class="n">factor</span> <span class="p">::</span><span class="o">=</span> <span class="p">(</span> <span class="n">expr</span> <span class="p">)</span>
    <span class="o">|</span>   <span class="n">NUM</span>
</pre></div>
</div>
<p>或者，以EBNF形式：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">term</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>

<span class="n">term</span> <span class="p">::</span><span class="o">=</span> <span class="n">factor</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span>

<span class="n">factor</span> <span class="p">::</span><span class="o">=</span> <span class="p">(</span> <span class="n">expr</span> <span class="p">)</span>
    <span class="o">|</span>   <span class="n">NUM</span>
</pre></div>
</div>
<p>在EBNF中，被包含在 <code class="docutils literal notranslate"><span class="pre">{...}*</span></code> 中的规则是可选的。<a href="#id4"><span class="problematic" id="id5">*</span></a>代表0次或多次重复(跟正则表达式中意义是一样的)。</p>
<p>现在，如果你对BNF的工作机制还不是很明白的话，就把它当做是一组左右符号可相互替换的规则。
一般来讲，解析的原理就是你利用BNF完成多个替换和扩展以匹配输入文本和语法规则。
为了演示，假设你正在解析形如 <code class="docutils literal notranslate"><span class="pre">3</span> <span class="pre">+</span> <span class="pre">4</span> <span class="pre">*</span> <span class="pre">5</span></code> 的表达式。
这个表达式先要通过使用2.18节中介绍的技术分解为一组令牌流。
结果可能是像下列这样的令牌序列：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">NUM</span> <span class="o">+</span> <span class="n">NUM</span> <span class="o">*</span> <span class="n">NUM</span>
</pre></div>
</div>
<p>在此基础上， 解析动作会试着去通过替换操作匹配语法到输入令牌：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">expr</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">term</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">factor</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">term</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">factor</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">NUM</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span><span class="p">}</span><span class="o">*</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">NUM</span> <span class="o">*</span> <span class="n">factor</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">NUM</span> <span class="o">*</span> <span class="n">NUM</span> <span class="p">{</span> <span class="p">(</span><span class="o">*|/</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">NUM</span> <span class="o">*</span> <span class="n">NUM</span> <span class="p">{</span> <span class="p">(</span><span class="o">+|-</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>
<span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">NUM</span> <span class="o">+</span> <span class="n">NUM</span> <span class="o">*</span> <span class="n">NUM</span>
</pre></div>
</div>
<p>下面所有的解析步骤可能需要花点时间弄明白，但是它们原理都是查找输入并试着去匹配语法规则。
第一个输入令牌是NUM，因此替换首先会匹配那个部分。
一旦匹配成功，就会进入下一个令牌+，以此类推。
当已经确定不能匹配下一个令牌的时候，右边的部分(比如 <code class="docutils literal notranslate"><span class="pre">{</span> <span class="pre">(*/)</span> <span class="pre">factor</span> <span class="pre">}*</span></code> )就会被清理掉。
在一个成功的解析中，整个右边部分会完全展开来匹配输入令牌流。</p>
<p>有了前面的知识背景，下面我们举一个简单示例来展示如何构建一个递归下降表达式求值程序：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="ch">#!/usr/bin/env python</span>
<span class="c1"># -*- encoding: utf-8 -*-</span>
<span class="sd">&quot;&quot;&quot;</span>
<span class="sd">Topic: 下降解析器</span>
<span class="sd">Desc :</span>
<span class="sd">&quot;&quot;&quot;</span>
<span class="kn">import</span> <span class="nn">re</span>
<span class="kn">import</span> <span class="nn">collections</span>

<span class="c1"># Token specification</span>
<span class="n">NUM</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;NUM&gt;\d+)&#39;</span>
<span class="n">PLUS</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;PLUS&gt;\+)&#39;</span>
<span class="n">MINUS</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;MINUS&gt;-)&#39;</span>
<span class="n">TIMES</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;TIMES&gt;\*)&#39;</span>
<span class="n">DIVIDE</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;DIVIDE&gt;/)&#39;</span>
<span class="n">LPAREN</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;LPAREN&gt;\()&#39;</span>
<span class="n">RPAREN</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;RPAREN&gt;\))&#39;</span>
<span class="n">WS</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;(?P&lt;WS&gt;\s+)&#39;</span>

<span class="n">master_pat</span> <span class="o">=</span> <span class="n">re</span><span class="o">.</span><span class="n">compile</span><span class="p">(</span><span class="s1">&#39;|&#39;</span><span class="o">.</span><span class="n">join</span><span class="p">([</span><span class="n">NUM</span><span class="p">,</span> <span class="n">PLUS</span><span class="p">,</span> <span class="n">MINUS</span><span class="p">,</span> <span class="n">TIMES</span><span class="p">,</span>
                                  <span class="n">DIVIDE</span><span class="p">,</span> <span class="n">LPAREN</span><span class="p">,</span> <span class="n">RPAREN</span><span class="p">,</span> <span class="n">WS</span><span class="p">]))</span>
<span class="c1"># Tokenizer</span>
<span class="n">Token</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">namedtuple</span><span class="p">(</span><span class="s1">&#39;Token&#39;</span><span class="p">,</span> <span class="p">[</span><span class="s1">&#39;type&#39;</span><span class="p">,</span> <span class="s1">&#39;value&#39;</span><span class="p">])</span>


<span class="k">def</span> <span class="nf">generate_tokens</span><span class="p">(</span><span class="n">text</span><span class="p">):</span>
    <span class="n">scanner</span> <span class="o">=</span> <span class="n">master_pat</span><span class="o">.</span><span class="n">scanner</span><span class="p">(</span><span class="n">text</span><span class="p">)</span>
    <span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="nb">iter</span><span class="p">(</span><span class="n">scanner</span><span class="o">.</span><span class="n">match</span><span class="p">,</span> <span class="bp">None</span><span class="p">):</span>
        <span class="n">tok</span> <span class="o">=</span> <span class="n">Token</span><span class="p">(</span><span class="n">m</span><span class="o">.</span><span class="n">lastgroup</span><span class="p">,</span> <span class="n">m</span><span class="o">.</span><span class="n">group</span><span class="p">())</span>
        <span class="k">if</span> <span class="n">tok</span><span class="o">.</span><span class="n">type</span> <span class="o">!=</span> <span class="s1">&#39;WS&#39;</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">tok</span>


<span class="c1"># Parser</span>
<span class="k">class</span> <span class="nc">ExpressionEvaluator</span><span class="p">:</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    Implementation of a recursive descent parser. Each method</span>
<span class="sd">    implements a single grammar rule. Use the ._accept() method</span>
<span class="sd">    to test and accept the current lookahead token. Use the ._expect()</span>
<span class="sd">    method to exactly match and discard the next token on on the input</span>
<span class="sd">    (or raise a SyntaxError if it doesn&#39;t match).</span>
<span class="sd">    &#39;&#39;&#39;</span>

    <span class="k">def</span> <span class="nf">parse</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">text</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">tokens</span> <span class="o">=</span> <span class="n">generate_tokens</span><span class="p">(</span><span class="n">text</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">tok</span> <span class="o">=</span> <span class="bp">None</span>  <span class="c1"># Last symbol consumed</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">nexttok</span> <span class="o">=</span> <span class="bp">None</span>  <span class="c1"># Next symbol tokenized</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_advance</span><span class="p">()</span>  <span class="c1"># Load first lookahead token</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">expr</span><span class="p">()</span>

    <span class="k">def</span> <span class="nf">_advance</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Advance one token ahead&#39;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">tok</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">nexttok</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">nexttok</span><span class="p">,</span> <span class="nb">next</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">tokens</span><span class="p">,</span> <span class="bp">None</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">_accept</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">toktype</span><span class="p">):</span>
        <span class="s1">&#39;Test and consume the next token if it matches toktype&#39;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">nexttok</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">nexttok</span><span class="o">.</span><span class="n">type</span> <span class="o">==</span> <span class="n">toktype</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_advance</span><span class="p">()</span>
            <span class="k">return</span> <span class="bp">True</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">False</span>

    <span class="k">def</span> <span class="nf">_expect</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">toktype</span><span class="p">):</span>
        <span class="s1">&#39;Consume next token if it matches toktype or raise SyntaxError&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="n">toktype</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">SyntaxError</span><span class="p">(</span><span class="s1">&#39;Expected &#39;</span> <span class="o">+</span> <span class="n">toktype</span><span class="p">)</span>

    <span class="c1"># Grammar rules follow</span>
    <span class="k">def</span> <span class="nf">expr</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s2">&quot;expression ::= term { (&#39;+&#39;|&#39;-&#39;) term }*&quot;</span>
        <span class="n">exprval</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">term</span><span class="p">()</span>
        <span class="k">while</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;PLUS&#39;</span><span class="p">)</span> <span class="ow">or</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;MINUS&#39;</span><span class="p">):</span>
            <span class="n">op</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">tok</span><span class="o">.</span><span class="n">type</span>
            <span class="n">right</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">term</span><span class="p">()</span>
            <span class="k">if</span> <span class="n">op</span> <span class="o">==</span> <span class="s1">&#39;PLUS&#39;</span><span class="p">:</span>
                <span class="n">exprval</span> <span class="o">+=</span> <span class="n">right</span>
            <span class="k">elif</span> <span class="n">op</span> <span class="o">==</span> <span class="s1">&#39;MINUS&#39;</span><span class="p">:</span>
                <span class="n">exprval</span> <span class="o">-=</span> <span class="n">right</span>
        <span class="k">return</span> <span class="n">exprval</span>

    <span class="k">def</span> <span class="nf">term</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s2">&quot;term ::= factor { (&#39;*&#39;|&#39;/&#39;) factor }*&quot;</span>
        <span class="n">termval</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">factor</span><span class="p">()</span>
        <span class="k">while</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;TIMES&#39;</span><span class="p">)</span> <span class="ow">or</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;DIVIDE&#39;</span><span class="p">):</span>
            <span class="n">op</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">tok</span><span class="o">.</span><span class="n">type</span>
            <span class="n">right</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">factor</span><span class="p">()</span>
            <span class="k">if</span> <span class="n">op</span> <span class="o">==</span> <span class="s1">&#39;TIMES&#39;</span><span class="p">:</span>
                <span class="n">termval</span> <span class="o">*=</span> <span class="n">right</span>
            <span class="k">elif</span> <span class="n">op</span> <span class="o">==</span> <span class="s1">&#39;DIVIDE&#39;</span><span class="p">:</span>
                <span class="n">termval</span> <span class="o">/=</span> <span class="n">right</span>
        <span class="k">return</span> <span class="n">termval</span>

    <span class="k">def</span> <span class="nf">factor</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s2">&quot;factor ::= NUM | ( expr )&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;NUM&#39;</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">int</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">tok</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
        <span class="k">elif</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;LPAREN&#39;</span><span class="p">):</span>
            <span class="n">exprval</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">expr</span><span class="p">()</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_expect</span><span class="p">(</span><span class="s1">&#39;RPAREN&#39;</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">exprval</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">SyntaxError</span><span class="p">(</span><span class="s1">&#39;Expected NUMBER or LPAREN&#39;</span><span class="p">)</span>


<span class="k">def</span> <span class="nf">descent_parser</span><span class="p">():</span>
    <span class="n">e</span> <span class="o">=</span> <span class="n">ExpressionEvaluator</span><span class="p">()</span>
    <span class="k">print</span><span class="p">(</span><span class="n">e</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2&#39;</span><span class="p">))</span>
    <span class="k">print</span><span class="p">(</span><span class="n">e</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2 + 3&#39;</span><span class="p">))</span>
    <span class="k">print</span><span class="p">(</span><span class="n">e</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2 + 3 * 4&#39;</span><span class="p">))</span>
    <span class="k">print</span><span class="p">(</span><span class="n">e</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2 + (3 + 4) * 5&#39;</span><span class="p">))</span>
    <span class="c1"># print(e.parse(&#39;2 + (3 + * 4)&#39;))</span>
    <span class="c1"># Traceback (most recent call last):</span>
    <span class="c1">#    File &quot;&lt;stdin&gt;&quot;, line 1, in &lt;module&gt;</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 40, in parse</span>
    <span class="c1">#    return self.expr()</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 67, in expr</span>
    <span class="c1">#    right = self.term()</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 77, in term</span>
    <span class="c1">#    termval = self.factor()</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 93, in factor</span>
    <span class="c1">#    exprval = self.expr()</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 67, in expr</span>
    <span class="c1">#    right = self.term()</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 77, in term</span>
    <span class="c1">#    termval = self.factor()</span>
    <span class="c1">#    File &quot;exprparse.py&quot;, line 97, in factor</span>
    <span class="c1">#    raise SyntaxError(&quot;Expected NUMBER or LPAREN&quot;)</span>
    <span class="c1">#    SyntaxError: Expected NUMBER or LPAREN</span>


<span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">&#39;__main__&#39;</span><span class="p">:</span>
    <span class="n">descent_parser</span><span class="p">()</span>
</pre></div>
</div>
</div>
<div class="section" id="id6">
<h2>讨论<a class="headerlink" href="#id6" title="Permalink to this headline">¶</a></h2>
<p>文本解析是一个很大的主题， 一般会占用学生学习编译课程时刚开始的三周时间。
如果你在找寻关于语法，解析算法等相关的背景知识的话，你应该去看一下编译器书籍。
很显然，关于这方面的内容太多，不可能在这里全部展开。</p>
<p>尽管如此，编写一个递归下降解析器的整体思路是比较简单的。
开始的时候，你先获得所有的语法规则，然后将其转换为一个函数或者方法。
因此如果你的语法类似这样：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">term</span> <span class="p">{</span> <span class="p">(</span><span class="s1">&#39;+&#39;</span><span class="o">|</span><span class="s1">&#39;-&#39;</span><span class="p">)</span> <span class="n">term</span> <span class="p">}</span><span class="o">*</span>

<span class="n">term</span> <span class="p">::</span><span class="o">=</span> <span class="n">factor</span> <span class="p">{</span> <span class="p">(</span><span class="s1">&#39;*&#39;</span><span class="o">|</span><span class="s1">&#39;/&#39;</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span>

<span class="n">factor</span> <span class="p">::</span><span class="o">=</span> <span class="s1">&#39;(&#39;</span> <span class="n">expr</span> <span class="s1">&#39;)&#39;</span>
    <span class="o">|</span> <span class="n">NUM</span>
</pre></div>
</div>
<p>你应该首先将它们转换成一组像下面这样的方法：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">ExpressionEvaluator</span><span class="p">:</span>
    <span class="o">...</span>
    <span class="k">def</span> <span class="nf">expr</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
    <span class="o">...</span>
    <span class="k">def</span> <span class="nf">term</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
    <span class="o">...</span>
    <span class="k">def</span> <span class="nf">factor</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
    <span class="o">...</span>
</pre></div>
</div>
<p>每个方法要完成的任务很简单 - 它必须从左至右遍历语法规则的每一部分，处理每个令牌。
从某种意义上讲，方法的目的就是要么处理完语法规则，要么产生一个语法错误。
为了这样做，需采用下面的这些实现方法：</p>
<ul class="simple">
<li>如果规则中的下个符号是另外一个语法规则的名字(比如term或factor)，就简单的调用同名的方法即可。
这就是该算法中”下降”的由来 - 控制下降到另一个语法规则中去。
有时候规则会调用已经执行的方法(比如，在 <code class="docutils literal notranslate"><span class="pre">factor</span> <span class="pre">::=</span> <span class="pre">'('expr</span> <span class="pre">')'</span></code> 中对expr的调用)。
这就是算法中”递归”的由来。</li>
<li>如果规则中下一个符号是个特殊符号(比如()，你得查找下一个令牌并确认是一个精确匹配)。
如果不匹配，就产生一个语法错误。这一节中的 <code class="docutils literal notranslate"><span class="pre">_expect()</span></code> 方法就是用来做这一步的。</li>
<li>如果规则中下一个符号为一些可能的选择项(比如 + 或 -)，
你必须对每一种可能情况检查下一个令牌，只有当它匹配一个的时候才能继续。
这也是本节示例中 <code class="docutils literal notranslate"><span class="pre">_accept()</span></code> 方法的目的。
它相当于_expect()方法的弱化版本，因为如果一个匹配找到了它会继续，
但是如果没找到，它不会产生错误而是回滚(允许后续的检查继续进行)。</li>
<li>对于有重复部分的规则(比如在规则表达式 <code class="docutils literal notranslate"><span class="pre">::=</span> <span class="pre">term</span> <span class="pre">{</span> <span class="pre">('+'|'-')</span> <span class="pre">term</span> <span class="pre">}*</span></code> 中)，
重复动作通过一个while循环来实现。
循环主体会收集或处理所有的重复元素直到没有其他元素可以找到。</li>
<li>一旦整个语法规则处理完成，每个方法会返回某种结果给调用者。
这就是在解析过程中值是怎样累加的原理。
比如，在表达式求值程序中，返回值代表表达式解析后的部分结果。
最后所有值会在最顶层的语法规则方法中合并起来。</li>
</ul>
<p>尽管向你演示的是一个简单的例子，递归下降解析器可以用来实现非常复杂的解析。
比如，Python语言本身就是通过一个递归下降解析器去解释的。
如果你对此感兴趣，你可以通过查看Python源码文件Grammar/Grammar来研究下底层语法机制。
看完你会发现，通过手动方式去实现一个解析器其实会有很多的局限和不足之处。</p>
<p>其中一个局限就是它们不能被用于包含任何左递归的语法规则中。比如，加入你需要翻译下面这样一个规则：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">items</span> <span class="p">::</span><span class="o">=</span> <span class="n">items</span> <span class="s1">&#39;,&#39;</span> <span class="n">item</span>
    <span class="o">|</span> <span class="n">item</span>
</pre></div>
</div>
<p>为了这样做，你可能会像下面这样使用 <code class="docutils literal notranslate"><span class="pre">items()</span></code> 方法：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
    <span class="n">itemsval</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()</span>
    <span class="k">if</span> <span class="n">itemsval</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">_accept</span><span class="p">(</span><span class="s1">&#39;,&#39;</span><span class="p">):</span>
        <span class="n">itemsval</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">item</span><span class="p">())</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="n">itemsval</span> <span class="o">=</span> <span class="p">[</span> <span class="bp">self</span><span class="o">.</span><span class="n">item</span><span class="p">()</span> <span class="p">]</span>
</pre></div>
</div>
<p>唯一的问题是这个方法根本不能工作，事实上，它会产生一个无限递归错误。</p>
<p>关于语法规则本身你可能也会碰到一些棘手的问题。
比如，你可能想知道下面这个简单扼语法是否表述得当：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">expr</span> <span class="p">::</span><span class="o">=</span> <span class="n">factor</span> <span class="p">{</span> <span class="p">(</span><span class="s1">&#39;+&#39;</span><span class="o">|</span><span class="s1">&#39;-&#39;</span><span class="o">|</span><span class="s1">&#39;*&#39;</span><span class="o">|</span><span class="s1">&#39;/&#39;</span><span class="p">)</span> <span class="n">factor</span> <span class="p">}</span><span class="o">*</span>

<span class="n">factor</span> <span class="p">::</span><span class="o">=</span> <span class="s1">&#39;(&#39;</span> <span class="n">expression</span> <span class="s1">&#39;)&#39;</span>
    <span class="o">|</span> <span class="n">NUM</span>
</pre></div>
</div>
<p>这个语法看上去没啥问题，但是它却不能察觉到标准四则运算中的运算符优先级。
比如，表达式 <code class="docutils literal notranslate"><span class="pre">&quot;3</span> <span class="pre">+</span> <span class="pre">4</span> <span class="pre">*</span> <span class="pre">5&quot;</span></code> 会得到35而不是期望的23.
分开使用”expr”和”term”规则可以让它正确的工作。</p>
<p>对于复杂的语法，你最好是选择某个解析工具比如PyParsing或者是PLY。
下面是使用PLY来重写表达式求值程序的代码：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">ply.lex</span> <span class="kn">import</span> <span class="n">lex</span>
<span class="kn">from</span> <span class="nn">ply.yacc</span> <span class="kn">import</span> <span class="n">yacc</span>

<span class="c1"># Token list</span>
<span class="n">tokens</span> <span class="o">=</span> <span class="p">[</span> <span class="s1">&#39;NUM&#39;</span><span class="p">,</span> <span class="s1">&#39;PLUS&#39;</span><span class="p">,</span> <span class="s1">&#39;MINUS&#39;</span><span class="p">,</span> <span class="s1">&#39;TIMES&#39;</span><span class="p">,</span> <span class="s1">&#39;DIVIDE&#39;</span><span class="p">,</span> <span class="s1">&#39;LPAREN&#39;</span><span class="p">,</span> <span class="s1">&#39;RPAREN&#39;</span> <span class="p">]</span>
<span class="c1"># Ignored characters</span>
<span class="n">t_ignore</span> <span class="o">=</span> <span class="s1">&#39; </span><span class="se">\t\n</span><span class="s1">&#39;</span>
<span class="c1"># Token specifications (as regexs)</span>
<span class="n">t_PLUS</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;\+&#39;</span>
<span class="n">t_MINUS</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;-&#39;</span>
<span class="n">t_TIMES</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;\*&#39;</span>
<span class="n">t_DIVIDE</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;/&#39;</span>
<span class="n">t_LPAREN</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;\(&#39;</span>
<span class="n">t_RPAREN</span> <span class="o">=</span> <span class="sa">r</span><span class="s1">&#39;\)&#39;</span>

<span class="c1"># Token processing functions</span>
<span class="k">def</span> <span class="nf">t_NUM</span><span class="p">(</span><span class="n">t</span><span class="p">):</span>
    <span class="sa">r</span><span class="s1">&#39;\d+&#39;</span>
    <span class="n">t</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="nb">int</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
    <span class="k">return</span> <span class="n">t</span>

<span class="c1"># Error handler</span>
<span class="k">def</span> <span class="nf">t_error</span><span class="p">(</span><span class="n">t</span><span class="p">):</span>
    <span class="k">print</span><span class="p">(</span><span class="s1">&#39;Bad character: {!r}&#39;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">value</span><span class="p">[</span><span class="mi">0</span><span class="p">]))</span>
    <span class="n">t</span><span class="o">.</span><span class="n">skip</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>

<span class="c1"># Build the lexer</span>
<span class="n">lexer</span> <span class="o">=</span> <span class="n">lex</span><span class="p">()</span>

<span class="c1"># Grammar rules and handler functions</span>
<span class="k">def</span> <span class="nf">p_expr</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    expr : expr PLUS term</span>
<span class="sd">        | expr MINUS term</span>
<span class="sd">    &#39;&#39;&#39;</span>
    <span class="k">if</span> <span class="n">p</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">==</span> <span class="s1">&#39;+&#39;</span><span class="p">:</span>
        <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">p</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span>
    <span class="k">elif</span> <span class="n">p</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">==</span> <span class="s1">&#39;-&#39;</span><span class="p">:</span>
        <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span>


<span class="k">def</span> <span class="nf">p_expr_term</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    expr : term</span>
<span class="sd">    &#39;&#39;&#39;</span>
    <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>


<span class="k">def</span> <span class="nf">p_term</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    term : term TIMES factor</span>
<span class="sd">    | term DIVIDE factor</span>
<span class="sd">    &#39;&#39;&#39;</span>
    <span class="k">if</span> <span class="n">p</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">==</span> <span class="s1">&#39;*&#39;</span><span class="p">:</span>
        <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">p</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span>
    <span class="k">elif</span> <span class="n">p</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">==</span> <span class="s1">&#39;/&#39;</span><span class="p">:</span>
        <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">/</span> <span class="n">p</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span>

<span class="k">def</span> <span class="nf">p_term_factor</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    term : factor</span>
<span class="sd">    &#39;&#39;&#39;</span>
    <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>

<span class="k">def</span> <span class="nf">p_factor</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    factor : NUM</span>
<span class="sd">    &#39;&#39;&#39;</span>
    <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>

<span class="k">def</span> <span class="nf">p_factor_group</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">    factor : LPAREN expr RPAREN</span>
<span class="sd">    &#39;&#39;&#39;</span>
    <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span>

<span class="k">def</span> <span class="nf">p_error</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="k">print</span><span class="p">(</span><span class="s1">&#39;Syntax error&#39;</span><span class="p">)</span>

<span class="n">parser</span> <span class="o">=</span> <span class="n">yacc</span><span class="p">()</span>
</pre></div>
</div>
<p>这个程序中，所有代码都位于一个比较高的层次。你只需要为令牌写正则表达式和规则匹配时的高阶处理函数即可。
而实际的运行解析器，接受令牌等等底层动作已经被库函数实现了。</p>
<p>下面是一个怎样使用得到的解析对象的例子：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">parser</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2&#39;</span><span class="p">)</span>
<span class="go">2</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">parser</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2+3&#39;</span><span class="p">)</span>
<span class="go">5</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">parser</span><span class="o">.</span><span class="n">parse</span><span class="p">(</span><span class="s1">&#39;2+(3+4)*5&#39;</span><span class="p">)</span>
<span class="go">37</span>
<span class="go">&gt;&gt;&gt;</span>
</pre></div>
</div>
<p>如果你想在你的编程过程中来点挑战和刺激，编写解析器和编译器是个不错的选择。
再次，一本编译器的书籍会包含很多底层的理论知识。不过很多好的资源也可以在网上找到。
Python自己的ast模块也值得去看一下。</p>
</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="p20_perform_text_operations_on_byte_string.html" class="btn btn-neutral float-right" title="2.20 字节字符串上的字符串操作" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="p18_tokenizing_text.html" class="btn btn-neutral" title="2.18 字符串令牌解析" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2017, 熊能.

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  

    <script type="text/javascript">
        var DOCUMENTATION_OPTIONS = {
            URL_ROOT:'../',
            VERSION:'3.0.0',
            LANGUAGE:'None',
            COLLAPSE_INDEX:false,
            FILE_SUFFIX:'.html',
            HAS_SOURCE:  true,
            SOURCELINK_SUFFIX: '.txt'
        };
    </script>
      <script type="text/javascript" src="../_static/jquery.js"></script>
      <script type="text/javascript" src="../_static/underscore.js"></script>
      <script type="text/javascript" src="../_static/doctools.js"></script>

  

  <script type="text/javascript" src="../_static/js/theme.js"></script>

  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script> 

</body>
</html>